1374D - Zero Remainder Array - CodeForces Solution

math sortings two pointers *1400

Please click on ads to support us..

Python Code: 

from collections import Counter
for _ in range(int(input())):
    n,k=map(int,input().split())
    arr=list(map(int,input().split()))
    d=Counter()
    for i in arr:
        if i%k!=0:
            d[k-i%k]+=1
    ma=0
    for i in d:
        ma=max(ma,i+d[i]*k-k+1)
    print(ma)

C++ Code: 

#include<bits/stdc++.h>
using namespace std ;
 
#define ll long long 

int main(){
    
    int t; cin>>t ; 
    while(t--){
        
        ll n,k ; cin>>n>>k ; 
        ll arr[n] ; 
        for(int i=0; i<n; i++) {
            cin>>arr[i] ; 
            arr[i] = k - arr[i]%k ;  
            if(arr[i]==k){
                arr[i]=0 ; 
            }
        }
        
        sort(arr,arr+n) ; 
        ll ans = 0 ; 
        map<ll,ll>mp ; 
        
        for(int i=0; i<n; i++){
            if(arr[i]!=0 && mp[arr[i]]==0){
                mp[arr[i]] = arr[i] ; 
                ans = max(ans,arr[i]) ; 
            }
            else if(arr[i]!=0 && mp[arr[i]]!=0){
                ans = max(ans,k+mp[arr[i]]) ; 
                mp[arr[i]] += k ; 
            }
        }  
        
        if(ans==0){
            ans=-1 ; 
        }
        
        cout<<ans+1<<endl;              
    }
}


Comments

Submit
0 Comments
More Questions

1475E - Advertising Agency
1345B - Card Constructions
1077B - Disturbed People
653A - Bear and Three Balls
794A - Bank Robbery
157A - Game Outcome
3B - Lorry
1392A - Omkar and Password
489A - SwapSort
932A - Palindromic Supersequence
433A - Kitahara Haruki's Gift
672A - Summer Camp
1277A - Happy Birthday Polycarp
577A - Multiplication Table
817C - Really Big Numbers
1355A - Sequence with Digits
977B - Two-gram
993A - Two Squares
1659D - Reverse Sort Sum
1659A - Red Versus Blue
1659B - Bit Flipping
1480B - The Great Hero
1519B - The Cake Is a Lie
1659C - Line Empire
515A - Drazil and Date
1084B - Kvass and the Fair Nut
1101A - Minimum Integer
985D - Sand Fortress
1279A - New Year Garland
1279B - Verse For Santa